"""
heapq 模块提供了堆队列算法的实现。堆是一种特殊的树形数据结构，其中每个父节点的值都小于或等于其所有子节点的值（最小堆），
或者每个父节点的值都大于或等于其所有子节点的值（最大堆）。heapq 默认实现的是最小堆。


主要特点
1. 高效的操作：
- 插入和删除操作的时间复杂度为 O(log n)。
- 获取最小元素的时间复杂度为 O(1)。
2. 基于列表的实现：
- heapq 使用列表来存储堆中的元素，并通过索引计算来维护堆的性质。
3. 线程不安全：
- heapq 的操作不是线程安全的，如果需要在多线程环境中使用，需要自行处理同步问题。

使用场景
1. 优先队列：
- 在需要按优先级处理任务的场景中，可以使用 heapq 来实现优先队列。例如，操作系统中的进程调度、网络包处理等。
2. Top K 问题：
- 当你需要找到数据集中最大的 k 个元素或最小的 k 个元素时，可以使用 heapq 来高效地解决这个问题。例如，在推荐系统中找到用户最感兴趣的 k 个项目。
3. 合并多个已排序的输入：
- 如果你有多个已排序的输入流，可以使用 heapq.merge 来高效地合并它们。例如，在日志处理中合并多个日志文件。
4. 动态中位数：
- 在需要动态维护一组数据的中位数时，可以使用两个堆（一个最大堆和一个最小堆）来实现。例如，在实时数据分析中计算滑动窗口的中位数
"""
import heapq

# 1. 创建堆
data = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(data)
print(data)  # 输出: [1, 1, 2, 3, 5, 9, 4, 6]

# 2. 插入元素

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)  # 输出: [3, 5, 7]
heap.clear()

# 3. 删除最小元素
heap = [3, 5, 7]
smallest = heapq.heappop(heap)
print(smallest)  # 输出: 3
print(heap)  # 输出: [5, 7]

# 4. 获取最小元素 heap[0]：直接访问堆顶元素（最小元素）
heap = [3, 5, 7]
print(heap[0])  # 输出: 3

# 5. 替换最小元素 heapreplace(heap, item)：弹出堆顶元素并推入新元素 item，效率高于 heappop 后再 heappush

heap = [3, 5, 7]
new_smallest = heapq.heapreplace(heap, 1)
print(new_smallest)  # 输出: 3
print(heap)  # 输出: [1, 5, 7]

# 6. 查找 n 个最大的元素：nlargest(n, iterable, key=None)：返回 iterable 中 n 个最大的元素
data = [3, 1, 4, 1, 5, 9, 2, 6]
largest = heapq.nlargest(3, data)
print(largest)  # 输出: [9, 6, 5]

# 7. 查找n个最小的元素
data = [3, 1, 4, 1, 5, 9, 2, 6]
smallest = heapq.nsmallest(3, data)
print(smallest)  # 输出: [1, 1, 2]
